package graph;

import java.util.Arrays;
import java.util.Scanner;

/**
 * Folyd
 * 【题目描述】
 * 小明喜欢去公园散步，公园内布置了许多的景点，相互之间通过小路连接，小明希望在观看景点的同时，能够节省体力，走最短的路径。
 * 给定一个公园景点图，图中有 N 个景点（编号为 1 到 N），以及 M 条双向道路连接着这些景点。每条道路上行走的距离都是已知的。
 * 小明有 Q 个观景计划，每个计划都有一个起点 start 和一个终点 end，表示他想从景点 start 前往景点 end。由于小明希望节省体力，他想知道每个观景计划中从起点到终点的最短路径长度。 请你帮助小明计算出每个观景计划的最短路径长度。
 * 【输入描述】
 * 第一行包含两个整数 N, M, 分别表示景点的数量和道路的数量。
 * 接下来的 M 行，每行包含三个整数 u, v, w，表示景点 u 和景点 v 之间有一条长度为 w 的双向道路。
 * 接下里的一行包含一个整数 Q，表示观景计划的数量。
 * 接下来的 Q 行，每行包含两个整数 start, end，表示一个观景计划的起点和终点。
 * 【输出描述】
 * 对于每个观景计划，输出一行表示从起点到终点的最短路径长度。如果两个景点之间不存在路径，则输出 -1。
 *
 * 动态规划的思想：
 * 节点i 到 节点j 的最短路径经过节点k     graph[i][k][k - 1] + graph[k][j][k - 1]
 * 节点i 到 节点j 的最短路径不经过节点k    graph[i][j][k - 1]
 *
 * 遍历顺序： 应该先遍历k，i和j的顺序无所谓
 */
public class Floyd {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int m = sc.nextInt();
        int[][][] graph = new int[n + 1][n + 1][n + 1];
        for (int i = 0; i < graph.length; i++) {
            for (int j = 0; j < graph[0].length; j++) {
                Arrays.fill(graph[i][j], 10005);
            }
        }
        for (int i = 0; i < m; i++) {
            int u = sc.nextInt();
            int v = sc.nextInt();
            int w = sc.nextInt();
            graph[u][v][0] = w;
            graph[v][u][0] = w;
        }

        for (int k = 1; k <= n; k++) {//k一定在外层，i和j无所谓
            for (int i = 1; i <= n; i++) {
                for (int j = 1; j <= n; j++) {
                    graph[i][j][k] = Math.min(graph[i][j][k - 1], graph[i][k][k - 1] + graph[k][j][k - 1]);
                }
            }
        }
        int q = sc.nextInt();
        for (int i = 0; i < q; i++) {
            int strat = sc.nextInt();
            int end = sc.nextInt();
            if (graph[strat][end][n] == 10005) System.out.println(-1);
            else System.out.println(graph[strat][end][n]);
        }
    }
}
